{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Swaps to Arrange a Binary Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排布二进制网格的最少交换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>n&nbsp;x n</code>&nbsp;的二进制网格&nbsp;<code>grid</code>，每一次操作中，你可以选择网格的&nbsp;<strong>相邻两行</strong>&nbsp;进行交换。</p>\n",
    "\n",
    "<p>一个符合要求的网格需要满足主对角线以上的格子全部都是 <strong>0</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 <strong>-1</strong>&nbsp;。</p>\n",
    "\n",
    "<p>主对角线指的是从&nbsp;<code>(1, 1)</code>&nbsp;到&nbsp;<code>(n, n)</code>&nbsp;的这些格子。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/02/fw.jpg\" style=\"height: 141px; width: 750px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[0,0,1],[1,1,0],[1,0,0]]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/02/e2.jpg\" style=\"height: 270px; width: 270px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>所有行都是一样的，交换相邻行无法使网格符合要求。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/02/e3.jpg\" style=\"height: 210px; width: 210px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0,0],[1,1,0],[1,1,1]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 200</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;要么是&nbsp;<code>0</code>&nbsp;要么是&nbsp;<code>1</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-swaps-to-arrange-a-binary-grid](https://leetcode.cn/problems/minimum-swaps-to-arrange-a-binary-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-swaps-to-arrange-a-binary-grid](https://leetcode.cn/problems/minimum-swaps-to-arrange-a-binary-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,1],[1,1,0],[1,0,0]]', '[[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]', '[[1,0,0],[1,1,0],[1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # 好像并不麻烦啊\n",
    "        # 判断存在的时候基本就可以找到规律了\n",
    "        # 必须存在至少 n-1 个 0  n-2 个零 ...\n",
    "        # if same , then greed\n",
    "        # 看似冒泡 但是应该可以 faster\n",
    "        # 注意“失智\"\"行为 为什么， 以及什么情况下容易失去， 习惯?\n",
    "        ans  = 0\n",
    "        n   = len(grid)\n",
    "        rm  = [0]*n\n",
    "        fd = n-1\n",
    "\n",
    "        while fd:\n",
    "            start = n-fd\n",
    "            skip= 0\n",
    "\n",
    "            t = True\n",
    "            i = 0\n",
    "            while i < n :\n",
    "                t = True\n",
    "                if rm[i]:\n",
    "                    i+=1\n",
    "                    t = False\n",
    "                    continue\n",
    "                for j in range(start, n):\n",
    "                    if grid[i][j]==1:\n",
    "                        t = False\n",
    "                        break\n",
    "                i+=1\n",
    "                if t:\n",
    "                    break\n",
    "                else:\n",
    "                    skip +=1\n",
    "            if t:\n",
    "                ans += skip\n",
    "                rm[i-1]=1\n",
    "            else:\n",
    "                return -1\n",
    "            fd-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        length = len(grid)\n",
    "        pos = [0]*length\n",
    "        for i in range(length):\n",
    "            for j in range(length-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        rs = 0\n",
    "        for i in range(length):\n",
    "            if pos[i]>i:\n",
    "                # 需要换\n",
    "                k = -1\n",
    "                for j in range(i+1, length):\n",
    "                    if pos[j] <= i:\n",
    "                        k = j\n",
    "                        break\n",
    "\n",
    "                if k == -1:\n",
    "                    return -1\n",
    "\n",
    "                rs += j-i\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            tmp = pos[k]\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j] = pos[j-1]\n",
    "            pos[i] = tmp\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    k = j\n",
    "                    ans += k - i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, idx, line):\n",
    "        for i in range(idx, len(line)):\n",
    "            if line[i] == 1:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if self.judge(i + 1, grid[j]):\n",
    "                    grid.insert(i, grid.pop(j))\n",
    "                    count += (j - i)\n",
    "                    break\n",
    "                if j + 1 == n:\n",
    "                    return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        # 计算每一行最靠上可以存在的位置\n",
    "        row_min_idx = []\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    row_min_idx.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                row_min_idx.append(0)\n",
    "\n",
    "        # print(row_min_idx)\n",
    "\n",
    "        # 贪心寻找、情景模拟\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 如果当前行已符合要求\n",
    "            if row_min_idx[i] <= i:\n",
    "                continue\n",
    "\n",
    "            # 如果当前行不符合要求，寻找符合要求的行\n",
    "            for j in range(i + 1, n):\n",
    "                if row_min_idx[j] <= i:\n",
    "                    ans += j - i\n",
    "                    row_min_idx = row_min_idx[:i] + [row_min_idx[j]] + row_min_idx[i:j] + row_min_idx[j + 1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "\n",
    "        def change(l):\n",
    "            ans = 0\n",
    "            for i in l[::-1]:\n",
    "                if i == 1:\n",
    "                    break\n",
    "                ans += 1\n",
    "            return ans \n",
    "        \n",
    "        grid = [change(i) for i in grid]\n",
    "        gg = sorted(grid)\n",
    "        for i in range(n):\n",
    "            if i > gg[i]:\n",
    "                return -1\n",
    "        \n",
    "        ans = 0\n",
    "        target = range(n-1,-1,-1)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if grid[j] >= target[i]:\n",
    "                    #print(i,j)\n",
    "                    ans += j-i\n",
    "                    grid[i+1:j+1] = grid[i:j]\n",
    "                    break\n",
    "            #print(grid)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def move(i, j):\n",
    "            tmp = pos[j]\n",
    "            # 枚举到i的后一行，i+1\n",
    "            for k in range(j, i, -1):\n",
    "                pos[k] = pos[k-1]\n",
    "            pos[i] = tmp\n",
    "\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的位置\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    # 需要交换的行\n",
    "                    k = j\n",
    "                    break\n",
    "            # 处理交换过程\n",
    "            \n",
    "            if k != -1:\n",
    "                move(i, j)\n",
    "            \n",
    "            if k == -1:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        pos=[-1]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]==1:\n",
    "                    pos[i]=j\n",
    "                    break\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            k=-1\n",
    "            for j in range(i,n):\n",
    "                if pos[j]<=i:\n",
    "                    ans+=j-i\n",
    "                    k=j\n",
    "                    break\n",
    "            if k==-1:\n",
    "                return -1\n",
    "            else:\n",
    "                for l in range(k,i,-1):\n",
    "                    pos[l],pos[l-1]=pos[l-1],pos[l]\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if not grid:\n",
    "            return 0\n",
    "        count = [0] * n\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    break\n",
    "                cnt += 1\n",
    "            count[i] = cnt\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t = n - i - 1\n",
    "            j = i\n",
    "            while j < n and count[j] < t:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                return -1\n",
    "            ans += j - i\n",
    "            while j > i:\n",
    "                count[j], count[j - 1] = count[j - 1], count[j]\n",
    "                j -= 1\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if not grid: return 0\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0:\n",
    "                j -= 1\n",
    "            zero_nums.append(n - j - 1)\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros:\n",
    "                j += 1\n",
    "            if j == len(zero_nums):\n",
    "                return -1\n",
    "            cnt += j - i\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1] = zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        #----- 每行，最右侧1的位置(index)\n",
    "        most_right_1 = [-1 for _ in range(n)]\n",
    "        for r in range(n):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if grid[r][c] == 1:\n",
    "                    most_right_1[r] = c\n",
    "                    break\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            find = False        #找到能交换的\n",
    "            find_r = -1         #能交换的行的行号（index）\n",
    "            #---- 从上往下搜，第一行可以交换的行\n",
    "            for rk in range(r, n):\n",
    "                if most_right_1[rk] <= r:\n",
    "                    find = True\n",
    "                    find_r = rk\n",
    "                    res += (rk - r)\n",
    "                    break \n",
    "            #---- 若没有合适的行\n",
    "            if find == False:\n",
    "                return -1\n",
    "            #---- 若有合适的行，交换\n",
    "            for rr in range(rk, r, -1):\n",
    "                most_right_1[rr], most_right_1[rr - 1] = most_right_1[rr - 1], most_right_1[rr]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        # 统计每一行 从右向左连续0的个数\n",
    "        n = len(grid)\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0: j -= 1\n",
    "            zero_nums.append(n - 1 - j)\n",
    "        # 贪心算法，从上到下查找满足条件的最小下标，即为交换到当前行的次数\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros: j += 1\n",
    "            \n",
    "            # 没找到则说明不满足条件\n",
    "            if j == len(zero_nums): return -1\n",
    "\n",
    "            # 增加交换次数\n",
    "            cnt += j - i\n",
    "            # 交换数值\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1]= zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        # 统计每一行 从右向左连续0的个数\n",
    "        n = len(grid)\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0: j -= 1\n",
    "            zero_nums.append(n - 1 - j)\n",
    "        # 贪心算法，从上到下查找满足条件的最小下标，即为交换到当前行的次数\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros: j += 1\n",
    "            \n",
    "            # 没找到则说明不满足条件\n",
    "            if j == len(zero_nums): return -1\n",
    "\n",
    "            # 增加交换次数\n",
    "            cnt += j - i\n",
    "            # 交换数值\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1]= zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        # 计算每一行最靠上可以存在的位置\n",
    "        row_min_idx = []\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    row_min_idx.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                row_min_idx.append(0)\n",
    "\n",
    "        # print(row_min_idx)\n",
    "\n",
    "        # 贪心寻找、情景模拟\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 如果当前行已符合要求\n",
    "            if row_min_idx[i] <= i:\n",
    "                continue\n",
    "\n",
    "            # 如果当前行不符合要求，寻找符合要求的行\n",
    "            for j in range(i + 1, n):\n",
    "                if row_min_idx[j] <= i:\n",
    "                    ans += j - i\n",
    "                    row_min_idx = row_min_idx[:i] + [row_min_idx[j]] + row_min_idx[i:j] + row_min_idx[j + 1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        last1=[]\n",
    "        n = len(grid)\n",
    "        for row in grid:\n",
    "            pos = -1\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if row[i]==1:\n",
    "                    pos=i\n",
    "                    break\n",
    "            last1.append(pos)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if last1[i]<=i:continue\n",
    "            found = False\n",
    "            for j in range(i+1,n):\n",
    "                if last1[j]<=i:\n",
    "                    found=True\n",
    "                    ans+=j-i\n",
    "                    for k in range(j,i,-1):\n",
    "                        last1[k],last1[k-1]=last1[k-1],last1[k]\n",
    "                    break\n",
    "            if not found: return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的位置\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    # 需要交换的行\n",
    "                    k = j\n",
    "                    break\n",
    "            # 处理交换过程\n",
    "            \n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "            \n",
    "            if k == -1:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "                n = len(grid)\n",
    "                f = [0 for i in range(n)]\n",
    "                for c in range(n-1,0,-1):\n",
    "                    for i,g in enumerate(grid):\n",
    "                        if g[n-c:] == [0] * c:\n",
    "                            f[i] = max(c,f[i])\n",
    "                c = n - 1;ans = 0\n",
    "                for i in range(n):\n",
    "                    if f[i] >= c:\n",
    "                        c -= 1\n",
    "                        continue\n",
    "                    flag = False\n",
    "                    for j in f[i+1:]:\n",
    "                        if j >= c:\n",
    "                            flag = True\n",
    "                            break\n",
    "                    if not flag:return -1\n",
    "                    for j in range(i+1,n):\n",
    "                        if f[j] >= c:\n",
    "                            ans += j - i\n",
    "                            for k in range(j,i,-1):\n",
    "                                f[k],f[k-1] = f[k-1],f[k]\n",
    "                            break\n",
    "                    \n",
    "                    c -= 1\n",
    "                    if c == 0:break\n",
    "                    \n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # 记录下来每一行的1的最后的位置\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            if  k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[ j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        zero_number_list = [0] * rows\n",
    "        swap_times = 0\n",
    "        for index in range(rows):\n",
    "            zero_number_list[index] = Check_Continuous_Zero_Number(grid, index)\n",
    "        target = columns - 1\n",
    "        for row in range(rows):\n",
    "            is_found = False\n",
    "            for target_row in range(row, rows):\n",
    "                if zero_number_list[target_row] >= target:\n",
    "                    swap_times += (target_row - row)\n",
    "                    is_found = True \n",
    "                    for swap_row in range(target_row, row, -1):\n",
    "                        zero_number_list[swap_row], zero_number_list[swap_row - 1]= zero_number_list[swap_row - 1], zero_number_list[swap_row] \n",
    "                    break \n",
    "            if is_found == False:\n",
    "                return -1\n",
    "            target -= 1\n",
    "        return swap_times\n",
    "\n",
    "def Check_Continuous_Zero_Number(grid, row):\n",
    "    zero_count = 0 \n",
    "    for cell in grid[row][::-1]:\n",
    "        if cell:\n",
    "            return zero_count \n",
    "        else:\n",
    "            zero_count += 1 \n",
    "    return zero_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "\n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # j <= i\n",
    "        # 预处理\n",
    "        # 统计每一行最后一个1出现的位置\n",
    "        n = len(grid)\n",
    "        g = [-1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]:\n",
    "                    g[i] = j\n",
    "                    break\n",
    "        # 枚举每一行\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 枚举哪一行的0满足要求\n",
    "            k = -1\n",
    "            for j in range(i,n):\n",
    "                if g[j] <= i:\n",
    "                    ans += (j-i)\n",
    "                    k= j\n",
    "                    break\n",
    "            if k != -1:\n",
    "                for x in range(k,i,-1):\n",
    "                    g[x],g[x-1] = g[x-1],g[x]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        l = [None] * n\n",
    "        for i in range(n):\n",
    "            k = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    break\n",
    "                k += 1\n",
    "            l[i] = k\n",
    "        \n",
    "        a = 0\n",
    "        for i, v in enumerate(l):\n",
    "            need = n-i-1\n",
    "            if v >= need:\n",
    "                continue\n",
    "            for j in range(i+1, n):\n",
    "                l[i], l[j] = l[j], l[i]\n",
    "                a+=1\n",
    "                if l[i] >= need:\n",
    "                    break\n",
    "            if l[i] < need:\n",
    "                return -1\n",
    "            \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的j\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            # 移动\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        lst = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            post = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j]:\n",
    "                    break\n",
    "                post += 1\n",
    "            lst.append(post)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            zero = n-1-i\n",
    "            if lst[i] < zero:\n",
    "                for j in range(i+1, n):\n",
    "                    if lst[j] >= zero:\n",
    "                        for x in range(j, i, -1):\n",
    "                            lst[x], lst[x-1] = lst[x-1], lst[x]\n",
    "                            ans += 1\n",
    "                        break   \n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # n*n的\n",
    "        # 第一步拿n-1的过去\n",
    "        # 第二步拿n-2的过去\n",
    "        # 直达拿1的过去\n",
    "        # 预处理\n",
    "        n = len(grid)\n",
    "        # 表示每一行最后一个1出现的位置\n",
    "        pos = [-1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i,n):\n",
    "                if i >= pos[j]:\n",
    "                    ans += j-i\n",
    "                    k = j\n",
    "                    break\n",
    "            if k != -1:\n",
    "                # 将顺序调整\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        gNew = []\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            if sum(grid[i]) == 0:\n",
    "                gNew.append(0)\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if grid[i][n - j - 1] == 1:\n",
    "                    gNew.append(n - j - 1)\n",
    "                    break\n",
    "        for i in range(n):\n",
    "            if gNew[i] <= i:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if gNew[j] <= i:\n",
    "                    count += j - i\n",
    "                    for k in range(j, i, -1):\n",
    "                        gNew[k] = gNew[k - 1]\n",
    "                    flag = 0\n",
    "                    break\n",
    "                flag = -1\n",
    "            if flag == -1:\n",
    "                return -1 \n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "        print(gNew)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            tmp = pos[k]\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j] = pos[j-1]\n",
    "            pos[i] = tmp\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    k = j\n",
    "                    ans += k - i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        zero_number_list = [0] * rows\n",
    "        swap_times = 0\n",
    "        for index in range(rows):\n",
    "            zero_number_list[index] = Check_Continuous_Zero_Number(grid, index)\n",
    "        target = columns - 1\n",
    "        for row in range(rows):\n",
    "            is_found = False\n",
    "            for target_row in range(row, rows):\n",
    "                if zero_number_list[target_row] >= target:\n",
    "                    swap_times += (target_row - row)\n",
    "                    is_found = True \n",
    "                    for swap_row in range(target_row, row, -1):\n",
    "                        zero_number_list[swap_row], zero_number_list[swap_row - 1]= zero_number_list[swap_row - 1], zero_number_list[swap_row] \n",
    "                    break \n",
    "            if is_found == False:\n",
    "                return -1\n",
    "            target -= 1\n",
    "        return swap_times\n",
    "\n",
    "def Check_Continuous_Zero_Number(grid, row):\n",
    "    zero_count = 0 \n",
    "    for cell in grid[row][::-1]:\n",
    "        if cell:\n",
    "            return zero_count \n",
    "        else:\n",
    "            zero_count += 1 \n",
    "    return zero_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = [0] * n\n",
    "        # m表示每行的后缀0个数\n",
    "        for i in range(n):\n",
    "            m[i] = n\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    m[i] = n - j - 1\n",
    "                    break\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for k in range(n):\n",
    "                if m[k] == -1: continue\n",
    "                if m[k] >= n - i - 1:\n",
    "                    res += t\n",
    "                    m[k] = -1\n",
    "                    break\n",
    "                t += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            \n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        n = len(grid)\n",
    "        \n",
    "        ans = 0\n",
    "        left = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if j == n - 1:\n",
    "                    left[i][j] = int(grid[i][j] == 0)\n",
    "                elif grid[i][j] == 0:\n",
    "                    left[i][j] = left[i][j + 1] + 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            need = n - i - 1\n",
    "            if left[i][i + 1] == need:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while j < n and left[j][i + 1] < need:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                return -1\n",
    "            # print(i, j)\n",
    "            ans += j - i\n",
    "            for k in range(j, i, -1):\n",
    "                left[k], left[k - 1] = left[k - 1], left[k]\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        gNew = []\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            if sum(grid[i]) == 0:\n",
    "                gNew.append(0)\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if grid[i][n - j - 1] == 1:\n",
    "                    gNew.append(n - j - 1)\n",
    "                    break\n",
    "        for i in range(n):\n",
    "            print(gNew)\n",
    "            if gNew[i] <= i:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if gNew[j] <= i:\n",
    "                    count += j - i\n",
    "                    for k in range(j, i, -1):\n",
    "                        gNew[k] = gNew[k - 1]\n",
    "                    flag = 0\n",
    "                    break\n",
    "                flag = -1\n",
    "            if flag == -1:\n",
    "                return -1 \n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "        print(gNew)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = [0] * n\n",
    "        # m表示每行的后缀0个数\n",
    "        for i in range(n):\n",
    "            m[i] = n\n",
    "            for j in reversed(range(n)):\n",
    "                if grid[i][j] == 1:\n",
    "                    m[i] = n - j - 1\n",
    "                    break\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for k in range(n):\n",
    "                if m[k] == -1: continue\n",
    "                if m[k] >= n - i - 1:\n",
    "                    res += t\n",
    "                    m[k] = -1\n",
    "                    break\n",
    "                t += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        tail = [0] * n\n",
    "        for i in range(n): # 求每一行末尾连续 0 个数\n",
    "            cnt = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    tail[i] = j\n",
    "                    break\n",
    "                cnt += 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if tail[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            if -1 == k:\n",
    "                return -1\n",
    "            else:\n",
    "                for j in range(k, i, - 1):\n",
    "                    tail[j], tail[j-1] = tail[j-1],tail[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        n_0 = []\n",
    "        for r in grid:\n",
    "            temp = 0\n",
    "            for i in range(n-1, -1, -1):\n",
    "                if r[i] == 0:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    break\n",
    "            n_0.append(temp)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(len(n_0)):\n",
    "                if n_0[j] >= n-1-i:\n",
    "                    ans += j\n",
    "                    n_0 = n_0[:j] + n_0[j+1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
